package com.zhang.study.chapter03;

import com.zhang.study.chapter03.node.DoubleNode;

import java.util.ArrayList;
import java.util.List;

import static com.zhang.util.NodeUtil.*;

/**
 * @author zhang
 * @description 双向链表反转
 */
public class Code02_DoubleNodeReverse {

    /**
     * 翻转双链表
     *
     * @param head 头结点
     * @return 翻转后的头结点
     */
    public static DoubleNode reverse(DoubleNode head) {
       if(head==null){
           return null;
       }
       DoubleNode pre = null;
       DoubleNode next = null;
       while (head!=null){
           next = head.next;
           head.next = pre;
           head.previous = next;
           pre = head;
           head = next;
       }

        return pre;
    }


    public static DoubleNode testReverseDoubleList(DoubleNode head) {
        if (head == null) {
            return null;
        }
        List<DoubleNode> list = new ArrayList<>();
        while (head != null) {
            list.add(head);
            head = head.next;
        }
        list.get(0).next = null;
        DoubleNode pre = list.get(0);
        for (int i = 1; i < list.size(); i++) {
            DoubleNode cur = list.get(i);
            cur.previous = null;
            cur.next = pre;
            pre.previous = cur;
            pre = cur;
        }
        return list.get(list.size() - 1);
    }

    public static void main(String[] args) {
        int len = 500;
        int value = 1001;
        int testTime = 100000;
        System.out.println("test begin!");
        for (int i = 0; i < testTime; i++) {

            DoubleNode node3 = generateRandomDoubleList(len, value);
            List<Integer> list3 = getDoubleListOriginOrder(node3);
            node3 = reverse(node3);
            if (!checkDoubleListReverse(list3, node3)) {
                System.out.println("Oops1!");
            }

            DoubleNode node4 = generateRandomDoubleList(len, value);
            List<Integer> list4 = getDoubleListOriginOrder(node4);
            node4 = testReverseDoubleList(node4);
            if (!checkDoubleListReverse(list4, node4)) {
                System.out.println("Oops2!");
            }

        }
        System.out.println("test finish!");


    }

}
